import java.util.Arrays;

public class PriorityQueue {
    public int[] elem;
    public int usedSize;
 
    public PriorityQueue() {
        //构造函数
        this.elem=new int[10];

    }
 
    /**
     * 建堆的时间复杂度：
     *
     * @param array
     */
    public void createHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }//准备堆中的初始数据
        for (int parent = (usedSize-1-1)/2; parent >=0 ; parent--) {
            //usedsizze-1得到最后一个元素下标然后再-1再/2得到最后一个元素的根节点下标
            shiftDown(parent,usedSize);

        }
    }
 
    /**
     *
     * @param root 是每棵子树的根节点的下标
     * @param len  是每棵子树调整结束的结束条件
     * 向下调整的时间复杂度：O(logn)
     */
    private void shiftDown(int root,int len) {
        int parent=root;
        int child=(parent)*2+1;
        while(child<len){
            if(child+1<len&&elem[child]<elem[child+1]){
                child++;//确保有右子树 并且找出左右子树中较大的那个
            }
            if(elem[child]>elem[parent]){
                swap(elem[child],elem[parent] );
            }
            parent=child;
            child=parent*2+1;
        }//向下转型,使无序变为堆
    }
 
 
    /**
     * 入队：仍然要保持是大根堆
     * @param val
     */
    public void swap(int a,int b){
        int temp=a;
        a=b;
        b=temp;
    }
    public void push(int val) {
        if(isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);
        }//扩容
        elem[usedSize]=val;
        shiftUp(usedSize);
        usedSize++;



    }
 
    private void shiftUp(int child) {
        //向上转型,使新加入的元素放到自己应有的位置
        int parent=(child-1)/2;
        while(child>0){
            if(elem[child] > elem[parent]){
                swap(elem[child],elem[parent]);
                child=parent;
                parent=(child-1)/2;

            }else{
                break;
            }

        }



    }
 
    public boolean isFull() {
        return usedSize== elem.length;
    }
 
    /**
     * 出队【删除】：每次删除的都是优先级高的元素
     * 仍然要保持是大根堆
     */
    public void pollHeap() {
        swap(elem[0],elem[usedSize-1] );
        usedSize--;
        shiftDown(0,usedSize);


    }
 
    public boolean isEmpty() {
        return usedSize==0;

    }
 
    /**
     * 获取堆顶元素
     * @return
     */
    public int peekHeap() {
        return elem[0];


    }
}